package main

func longestPalindromeSubseq(s string) int {
    dp := make([][]int, len(s))
	for i := range s {
		dp[i] = make([]int, len(s))
	}
	for i := len(s) - 1; i >= 0; i-- {
		for j := range s {
			if i >= j {
				dp[i][j] = 0
			} else {
				if s[i] == s[j] {
					dp[i][j] = dp[i+1][j-1] + 2
				} else {
					if dp[i+1][j] > dp[i][j-1] {
						dp[i][j] = dp[i+1][j]
					} else {
						dp[i][j] = dp[i][j-1]
					}
				}
			}
		}
	}
	return dp[0][len(s)-1]
}